#include "stdafx.h"
#include "graph.h"



using std::vector;
using std::set;
using namespace std;


void CGraph::Kruskal() {
	
	/////// MAKE-SET
	int cV = GetCountV();
	int cE = GetCountE();
	//CGraph * drzewo = new CGraph( cV, cE, CGraph::Matrix );

	vector<vector<int>> sets(cV);
	vector<int>::reverse_iterator it2;
	for (int i=0; i<sets.size(); ++i )
	{
		sets[i].push_back(i + 1);
	}
	////// Edges tree
	//FillEdgesTree();
	set<edge>::iterator ite;
	set<edge> MDR;
	////// FIND-SET
	while(!edges.empty())
	{	
		//vector<vector<int>>::iterator a,b;
		vector<int> a, b;
		ite=edges.begin();
		//drzewo->AddUndirectEdge( (*ite).vA, (*ite).vB, (*ite).weight);
		int tmp = 0; int tmpi=0, tmpj=0;
		for (int i=0; (i<sets.size())&&(tmp!=2); ++i)
		{
			for (int j=0; j<sets[i].size(); ++j)
			{
				if(sets[i][j]==((*ite).vA))
				{
					a=sets[i];
					tmpi=i;
					tmp++;
				}
				if(sets[i][j]==((*ite).vB))
				{
					b=sets[i];
					tmpj=i;
					tmp++;
				}
			}
		
		}
		if(a!=b)
		{
			//printf("a");
			
			//sets.erase(find(sets.begin(),sets.end(),(*b)));
			//(*(find(sets.begin(),sets.end(),(*a)))).clear();
			vector<int> c;

			c.resize((int)a.size()+(int)b.size());
			merge(a.begin(),a.end(),b.begin(),b.end(), c.begin());
			sets.push_back(c);
			//sets.erase(sets[tmpi]);
			sets[tmpi].clear();
			sets[tmpj].clear();


			
			
			/*while(!b.empty())
			{
				it2=b.rbegin();
				a.push_back(*it2);
				b.pop_back();
			}*/
			MDR.insert(*ite);
		} 
		edges.erase(ite);
		
	}

	

		
	
}